package leetcode;

public class NumberOfDigitOne {

	public int countDigitOne(int n) {
        if(n < 0){
        	return 0;
        }
        int count = 0;
        //个位超过1时候，个位为1的个数为1，(1)十位大于等于2的时候，十位为1的个数为10(10 ~ 19)
        //百位大于等于2的时候，百位为1的个数为100(100 ~ 199)
        for(long k = 1; k <= n; k *= 10){
        	long r = n / k; 
        	long m = n % k;
        	//之所以r + 8是因为是以大于等于2为界
        	//比如15,十位为1的个数就没有10,那么就应该看十位是否为1，如果为1,m表示十位为1的个数
        	//k为1的时候是指求的个位为1的个数
        	//为10的时候是指求的十位为1的个数......
        	// let's start with ones' place and count how many ones at this place, set k = 1,
        	// as mentioned above, there's a one at ones' place in every 10 numbers, (1 11 21 ...)
        	// so how many 10 numbers do we have?
        	// The answer is (n / k) / 10.
        	
        	// Now let's count the ones in tens' place, set k = 10, 
        	// as mentioned above, there are 10 ones at tens' place in every 100 numbers(10 ~ 19   110~119)
        	// The answer is (n / k) / 10, and the number of ones at ten's place is (n / k) / 10 * 10
        	
        	// Take 10, 11, and 12 for example, if n is 10, we get (n / 1) / 10 * 1 = 1 ones at ones's place, 
        	// but for tens' place, we get (n / 10) / 10 * 10 = 0, that's not right, there should be a one at 
        	// tens' place! Calm down, from 10 to 19, we always have a one at tens's place, let m = n % k, 
        	// the number of ones at this special place is m + 1, so let's fix the formula to be:

        	// r / 10 * k + (r % 10 == 1 ? m + 1 : 0)
        	
        	// Wait, how about 20, 21 and 22
        	// Let's say 20, use the above formula we get 0 ones at tens' place, but it should be 10!
        	// since we know ,while digit is no less than 2, we should add corresponding count
        	// (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0)
        	//注意是m+1, 因为取余是0 ~ k - 1
        	//但是计数是1 ~ k
        	count += (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0);
        }
        return count;
    }
}
